package DataStructure.stack;

import java.util.Stack;

/**
 * 42. 接雨水 https://leetcode.cn/problems/trapping-rain-water/
 */
public class Trap {

    public static void main(String[] args) {
        new Trap().trap2(new int[]{0,1,0,2,1,0,1,2});
    }


    /**
     * 思路一：每次计算一洼水的volume，先从左向右遍历找出到最高墙之间的所有洼，再找出从右向左到最高墙的所有洼，得出volume总和。
     * 时间复杂度O(n),空间复杂度O(1)
     */
    public int trap(int[] height) {
        if(height == null || height.length < 3) {
            return 0;
        }
        int leftHeight = height[0];
        int oneVolume=0, sumVolume=0;
        //从左向右遍历找出到最高墙之间的所有洼
        for(int i=1;i < height.length;i++) {
            //leftHeight为一洼容器的左壁高度
            if(height[i] < leftHeight) {
                oneVolume += leftHeight - height[i];
            } else {
                //当找到比leftHeight更高的墙，则为一洼
                sumVolume += oneVolume;
                //更新leftHeight继续向后寻找容器
                oneVolume = 0;
                leftHeight = height[i];
            }
        }
        //再找出从右向左到最高墙的所有洼
        if(oneVolume != 0) {
            int rightHeight = height[height.length-1];
            oneVolume = 0;
            for(int i=height.length-2;height[i] < leftHeight;i--) {
                if(height[i] < rightHeight) {
                    oneVolume += rightHeight - height[i];
                } else {
                    sumVolume += oneVolume;
                    oneVolume = 0;
                    rightHeight = height[i];
                }
            }
        }
        return sumVolume+oneVolume;
    }

    /**
     * 思路二：利用栈的思想。
     * current指针扫描，小于等于栈顶的元素都入栈。
     * 若current遇到比栈顶大的元素则出栈栈顶元素a，计算栈中下一个元素b、a、current三者之间的容量。直到栈中没有比current更大的元素，current再继续扫描
     * 显然，current之前，低于a高度的水必然已被统计
     */
    public int trap2(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        int current = 0;
        while (current < height.length) {
            //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
            while (!stack.empty() && height[current] > height[stack.peek()]) {
                int h = height[stack.peek()]; //取出要出栈的元素
                stack.pop(); //出栈
                if (stack.empty()) { // 栈空就出去
                    break;
                }
                int distance = current - stack.peek() - 1; //两堵墙之前的距离。
                int min = Math.min(height[stack.peek()], height[current]);
                sum = sum + distance * (min - h);
            }
            stack.push(current); //当前指向的墙入栈
            current++; //指针后移
        }
        return sum;
    }
}
